package com.sheng.leetcode.year2022.swordfingeroffer.day24;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/22
 *<p>
 * 剑指 Offer 57 - II. 和为s的连续正数序列<p>
 *<p>
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。<p>
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。<p>
 *<p>
 * 示例 1：<p>
 * 输入：target = 9<p>
 * 输出：[[2,3,4],[4,5]]<p>
 *<p>
 * 示例 2：<p>
 * 输入：target = 15<p>
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]<p>
 *<p>
 * 限制：<p>
 *<p>
 * 1 <= target <= 10^5<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0057 {

    @Test
    public void test01() {
//        int target = 9;
        int target = 15;
        System.out.println(Arrays.deepToString(new Solution57().findContinuousSequence(target)));
    }
}
class Solution57 {
    List<List<Integer>> lists = new ArrayList<>();
    public int[][] findContinuousSequence(int target) {
        // 题目要求连续正整数序列(至少2个正整数)，范围应该是1 ~ (target / 2 + 1)
        // 滑块法，计算左右端点之间的和
        int left = 1, right = 1, sum = 0;
        while (left <= target / 2) {
            if (sum < target) {
                sum += right++;
            } else if (sum > target) {
                sum -= left++;
            } else {
                List<Integer> list = new ArrayList<>();
                for (int i = left; i < right; i++) {
                    list.add(i);
                }
                lists.add(list);
                sum -= left++;
            }
        }
        // 集合转二维数组
        return lists.stream().map(list -> list.stream().mapToInt(i -> i).toArray()).toArray(int[][]::new);
    }
}
